package es.ucm.fdi.lps.abadia.grafogeneral;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Vector;


/**
 * Esta clase representa una estructura de datos de tipo grafo, que consta
 * conjunto de v�rtices, y un conjunto de nodos para cada v�rtice
 * @author Alberto Moreno y Gabriel Voicila
 */
public class GrafoNoDirigido<T> {

	/**
	 * Referencia a Vertice que representa el inicio de la estructura grafo
	 */
	 private Vertice<T> v;
	 
	 /**
	  * Tama�o del grafo, n�mero de vertices de la lista
	  */
	 private int tamaño;
     
	 /** 
	  * Inicializa una estructura de grafo, apuntando a null su comienzo
	  * y su tama�o a 0
	  */
     public GrafoNoDirigido()
     {
             v=null;
             tamaño=0;
     }
     
     /**
      * @return tama�o actual del grafo (n�mero de v�rtices)
      * 
      */
     public int dameTamaño()
     {
    	 return tamaño;
     }
     
     /**
      * Comprueba que el par�metro entrante se encuentre
      * como informaci�n de alguno de los v�rtices del grafo
      * @param vertice, informaci�n a buscar en los v�rtices del grafo
      * @return booleano, falso si no se encuentra, true si est�
      */
     
     public boolean estaVertice(T vertice)
     {
         Vertice<T> aux=v;
         while((aux!=null)&&(aux.info!= vertice)) aux=aux.vertice_sig;
         return aux!=null;
     }
     
     /**
      * Comprueba si un grafo es vacio
      * @return booleano indicando si es vacio o no
      */
 
     public boolean esVacio()
     {
         return v==null;
     }
     
     /**
      * Devuelve la informaci�n el v�rtice correspondiente a una posici�n dada
      * @param i, posici�n del v�rtice a devolver. 
      * i nunca es mayor que el tama�o del grafo!
      * @return devuelve la informaci�n del v�rtice indicado por i
      */
     public T dameInfoVertice(int i)
     {
         Vertice<T> aux=v;
         int aux1= 0;
         while((aux!=null) && (aux1<i)) {
        	 aux=aux.vertice_sig;
        	 aux1++;
         }
         return aux.info;
     }
     
     /**
      * Devuelve el v�rtice que contenga la informaci�n que se pasa por par�metro
      * @param vertice, informaci�n a comprobar en la lista de v�rtices
      * @return aux, v�rtice con la informaci�n 
      */
     private Vertice<T> dameVertice(T infoVertice)
     {
         Vertice<T> aux=v;
         while((aux!=null)&&(aux.info!= infoVertice)) aux=aux.vertice_sig;
         return aux;
     }
     
     /**
      * Devuelve un vector que contiene los nodos correspondientes a un v�rtice dado
      * @param vertice del cual quieren devolverse los nodos
      * @return vector, contiene los nodos del vertice buscado
      */
     public Vector<T> nodosPorVertice(T vertice)
     {
    	 Vector <T> vector = new Vector<T>();
    	 Vertice<T> aux= v;
    	 while ((aux!=null) &&(aux.dameVertice()!=vertice)) aux=aux.vertice_sig;
    	 if (aux==null) return vector;
    	 else {
    		 	Nodo<T> nodoAux= aux.arista_sig;
    		 	while (nodoAux!=null){
    		 		vector.add(nodoAux.dameInfoNodo());
    		 		nodoAux= nodoAux.nodo_sig;
    		  }
    	 return vector;
    	 }
     }
    
     /**
      * A�ade un vertice al principio de la lista si ninguno de los v�rtices
      * del grafo contiene la informaci�n que se pasa como par�metro 
      * @param infoVertice, informaci�n a buscar en el listado de v�rtices
      * @return booleano, indicando si se a�adi� o no el v�rtice
      */
     
     public boolean aniadeVertice(T infoVertice)
     {
             Vertice<T> aux=v;
             while((aux!=null)&&(aux.info!= infoVertice)) aux=aux.vertice_sig;
             if(aux!=null) return false;
             else
             {
                   aux= new Vertice<T>(infoVertice);
                   aux.vertice_sig=v;
                   v=aux;
                   tamaño++;
                   return true;
             }
     }
     /**
      * Borra un v�rtice que contenga la informaci�n pasada como par�metro,
      * as� como su lista de nodos si se encuentra dicho v�rtice      
      * @param infoVertice
      * @return booleano, inddicando si se produjo o no la eliminaci�n
      */
     public boolean eliminaVertice(T infoVertice)
     {
             Vertice<T> aux=v;
             Vertice<T> anterior_aux=null;
             while((aux!=null)&&(aux.info!= infoVertice)){
                     anterior_aux=aux;
                     aux=aux.vertice_sig;
             }
             if(aux==null) return false;
             else{
                     borraAristasEntrantes(aux);
                     if(anterior_aux==null) v=v.vertice_sig; 
                     else anterior_aux.vertice_sig=aux.vertice_sig; 
                     tamaño--;
                     return true;
             }
     }
     
     /**
      * A�ade un nodo al v�rtice que contiene la informaci�n igual a 
      * infoVerticeOrigen
      * @param infoVerticeOrg, vertice origen
      * @param infoVerticeDestino, informaci�n correspondiente al v�rtice destino
      * @return booleano, indicando si se a�adi� el v�rtice o no
      */
    	 
     public boolean aniadeNodo(T infoVerticeOrg, T infoVerticeDestino)
     {
    	 Vertice<T> aux=v;
    	 while((aux!=null)&& (aux.info!=infoVerticeOrg)) aux= aux.vertice_sig;
    	 if (aux==null) return false;
    	 else
    	 {
    		 Vertice<T> auxVerticeDestino=v;
    		 while((auxVerticeDestino!=null)&&(auxVerticeDestino.info!=infoVerticeDestino)) auxVerticeDestino=auxVerticeDestino.vertice_sig;
    		 if(auxVerticeDestino==null) return false;
    		 else
    		 {
    			 Nodo<T> auxArista= new Nodo<T>(infoVerticeDestino);
    			 auxArista.destino= auxVerticeDestino;
    			 auxArista.nodo_sig= aux.arista_sig;
    			 aux.arista_sig= auxArista;
    			 return true;
    		 }
    	 }
     }
         
     /**
      * Elimina un nodo dado, borrando las referencias que haya a �l en
      * el resto del grafo
      * 
      * @param infoVerticeOrigen
      * @param infoVerticeDestino
      * @return booleano
      */
     public boolean eliminaNodo (T infoVerticeOrigen, T infoNodoDestino)
     {
    	 Vertice<T> aux= v;
    	 while ((aux!=null)&&(aux.info!=infoVerticeOrigen)) 
    	 {
    		 aux=aux.vertice_sig;
    	 }
    	 if (aux==null) return false;
    	 else
    	 {
    		 Nodo<T> auxSig= aux.arista_sig;
    		 Nodo<T> anteriorAuxSig= null;
    		 while((auxSig!=null)&&(auxSig.info!=infoNodoDestino))
    		 {
    			 anteriorAuxSig= auxSig;
    			 auxSig= auxSig.nodo_sig;
    		 }
    		 if (auxSig==null) return false;
    		 else
    		 {
    			 if (anteriorAuxSig==null) aux.arista_sig=auxSig.nodo_sig;
    			 else anteriorAuxSig.nodo_sig= auxSig.nodo_sig;
    			 return true;
    		 }
     	}
 	 }
     

     /**
      * Comprueba que un nodo se encuentre en el grafo
      * @param infoVerticeOrigen
      * @param infoNodoDestino
      * @return
      */
     public boolean esNodo(T infoVerticeOrigen, T infoNodoDestino)
     {
    	 Vertice<T> aux= v;
    	 while((aux!=null)&&(aux!= infoVerticeOrigen)) aux= aux.vertice_sig;
    	 if (aux==null) return false;
    	 else
    	 {
    		 Nodo<T> auxSig= aux.arista_sig;
    		 while((auxSig!=null)&&(auxSig.destino!= infoNodoDestino)) auxSig= auxSig.nodo_sig;
    		 return auxSig!=null;
    	 }
     }
     /**
      * Borra todas las referencias a nodos de un v�rtice a eliminar
      * @param verticeBorrar, v�rtice 
      */
     private void borraAristasEntrantes(Vertice<T> verticeBorrar)
     {
    	 Vertice<T> aux=v;
         while(aux!=null){
                 borraReferenciaArista(aux,verticeBorrar);
                 aux=aux.vertice_sig;
         }
     }
     /**
      * Se encarga de borrar cada una de las referencias a nodos de un v�rtice
      * dado 
      * @param org
      * @param vertice
      */
     private void borraReferenciaArista(Vertice<T> org, Vertice<T> vertice)
     {
    	 Nodo<T> aux= org.arista_sig;
    	 Nodo<T> anteriorAux= null;
    	 while((aux!=null)&&(aux.destino!=vertice))
    	 {
    		 anteriorAux= aux;
    		 aux=aux.nodo_sig;
    	 }
    	 if(aux!=null)
    	 {
    		 if (anteriorAux==null) org.arista_sig=aux.nodo_sig; //OJOJO!!!!
    		 else anteriorAux.nodo_sig=aux.nodo_sig;
    	 }
     }   
     
     
     /**
      * Devuelve todos los nodos adyacentes al v�rtice cuya informaci�n es 
      * igual que el param�tro infoVertice
      * @param infoVertice, contenido a buscar en la lista de v�rtices
      * @param c, conjunto de nodos 
      * @return c, conjunto de nodos modificado
      */
     public Set<T> conexionesPosibles (T infoVertice, Set<T> c)
     	{
    	 	Vertice<T> vAux= v;
    	 	while ((vAux!=null && vAux.info!= infoVertice))
    	 	{
    	 		vAux=vAux.vertice_sig;
    	 	}
    	 	if (vAux!=null) 
    	 	{
    	 		Nodo<T> aAux= vAux.arista_sig;
    	 		while (aAux!=null) 
    	 		{
    			  	c.add(aAux.info); 
    			  	aAux=aAux.nodo_sig;
    	 		}	 
    	 	} 
    	 	return c;
     	}
     
     /**
      * Devuelve todas las casillas adyacentes a partir de un n�mero de 
      * movimientos
      * 
      * @param casillaOrigen, casilla donde se encuentra el jugador
      * @param posiblesMovimientos, numero de movimientos permitidos
      * @return resultado, devuelve un conjunto con las habitaciones totales
      */
     public Set<T> conexionesPosibles(T casillaOrigen, int posiblesMovimientos)
     	 {
    	 	Set<T> resultado= new HashSet<T>();
    	 	resultado= conexionesPosibles(casillaOrigen, resultado);
    	 	Iterator<T> iter= resultado.iterator();
    	 	
    	 	if (posiblesMovimientos>0 && resultado.size()>0){
    	 		Set<T> c= new HashSet<T>(); // vertices a�adidos
    	 		c.add(casillaOrigen);
    	 		for (int i=1; i<posiblesMovimientos; i++){
    	 			Set<T> aux= new HashSet<T>();
    	 			while (iter.hasNext()){
    	 				if (!c.contains(iter)){
        	    	 		aux= conexionesPosibles(iter.next(), c); 
        	    	    	c.addAll(aux);
    	 				}
    	    	 	}
    	    	 	resultado.addAll(c);
    	 		}
    	 	}
       	 	if (resultado.contains(casillaOrigen)) resultado.remove(casillaOrigen);
    	    return resultado;    	    
    	 }
     	 
	     

}// Fin Grafo 
	